import random
from lib import *

def divlist(l,cohen=0.3,minObs=4,accept=lambda x:True):
  return div(summed(bagged(l,accept=accept)), cohen=cohen,minObs=minObs)

def bagged(l,accept=lambda x: True):
  out=Deep(); 
  for x in l: 
    if accept(x):
      out.push(x,x) 
  return out

def summed(d) :
  out={}
  for key,values in d.items():
    y = out[key] = Summary(key)
    for value in values: y.keep(value)
  return out

class Summary:
  def __init__(i,tag): i.tag=tag; i.rank=i.s = i.sq = i.n = 0
  def sigma(i)     : return ((i.sq-((i.s*i.s)/i.n))/(i.n-1))**0.5
  def mu(i)        : return i.s/i.n
  def keep(i,x)    : i.n += 1; i.s += x; i.sq += x*x; return x
  def keeps(i,lst) : [i.keep(x) for x in lst]       ; return lst
  def __lt__(i,j)  : return i.mu() < j.mu()
  def __str__(i)   : return strs(vars(i),{'mu':i.mu()})
  def __add__(i,j) :
    k = Summary('+'); k.s=i.s+j.s; k.sq=i.sq+j.sq; k.n=i.n+j.n 
    return k
  def __sub__(i,j) :
    k = Summary('-'); k.s=i.s-j.s; k.sq=i.sq-j.sq; k.n=i.n-j.n 
    return k

def div(bags,cohen=0.3,minObs=4):
  def interesting(mu0,mu1)    : return abs(mu0 - mu1) > big
  def xpect(mu,n0,mu0,n1,mu1) : return n0*(mu0 - mu)**2 + n1*(mu1 - mu)**2
  def where(all,overall,level,hi= -1) :
    lhs = all[0]
    cut= above = below = None
    for i in range(len(all)):
      if i==0: continue
      rhs = overall - lhs
      if lhs.n >= minObs:
         if rhs.n >= minObs:
            now = xpect(overall.mu(),lhs.n,lhs.mu(),rhs.n,rhs.mu()) 
            if now > hi and interesting(lhs.mu(),rhs.mu()):
               cut,hi,below,above  = i,now,lhs,rhs
      lhs = lhs + all[i]
    return cut,below,above
  def recurse(all,overall,id=1,level=0) :
    cut,below,above = where(all,overall,level)
    if not cut:
      for x in all: 
        x.rank = id
    else:
      id = recurse(all[:cut],below,id,level+1) + 1
      id = recurse(all[cut:],above,id,level+1)
    return id
  def patch(lst) :
    one = lst[0]
    rank = 1
    for two in lst[1:] :
      if two.rank > one.rank and two.mu() != one.mu():
         rank += 1
      two.rank = rank
      one = two
  ordered = sorted(bags.values())
  overall = reduce(lambda x,y:x+y,ordered) 
  big     = cohen * overall.sigma()
  recurse(ordered,overall)
  patch(ordered)
  out = {}
  for x in ordered: out[x.tag] = x
  return out
